#!/usr/bin/env python
# -*- encoding: utf-8 -*-
'''
@Author  :   JingV
@Version :   1.0
@Contact :   None
@License :   None
@Desc    :   None
'''


class Solution(object):
    def solveSudoku(self, board):
        board_row, board_column = len(board), len(board[0])

        # 处理9宫格出现的数字
        board_handled = []
        for i in range(board_row // 3):
            row_temp = []
            for j in range(board_column // 3):
                column_temp = []
                for x in range(i * 3, (i + 1) * 3):
                    for y in range(j * 3, (j + 1) * 3):
                        if board[x][y] != '.' and board[x][y] not in column_temp:
                            column_temp.append(board[x][y])
                row_temp.append(column_temp)
            board_handled.append(row_temp)

        def help(pos, the_board):
            pos_row, pos_column = pos[0], pos[1]

            # 获取下一个值为'.'的pos
            while the_board[pos_row][pos_column] != '.':
                # print('({}, {})'.format(pos_row, pos_column))
                pos_column += 1
                if pos_column >= board_column:
                    pos_row, pos_column = pos_row + 1, 0
                # 没有值为.的位置, 所有位置都已遍历完毕, 解题完成
                if pos_row >= board_row:
                    return True

            # 获取可能的数字
            avaliable_items = [str(_) for _ in range(1, 10)]
            for i in the_board[pos_row]:
                if i in avaliable_items:
                    avaliable_items.remove(i)
            for i in [item[pos_column] for item in the_board]:
                if i in avaliable_items:
                    avaliable_items.remove(i)
            for i in board_handled[pos_row // 3][pos_column // 3]:
                if i in avaliable_items:
                    avaliable_items.remove(i)

            # 当前位置没有可以填入的数字, 不合法
            if len(avaliable_items) == 0:
                return False
            # 依次尝试填入合法数字
            for i in avaliable_items:
                # print('({}, {})'.format(pos_row, pos_column))
                the_board[pos_row][pos_column] = i
                # 如果填入这个值, 那么这个值应该在board_handled中出现
                board_handled[pos_row // 3][pos_column // 3].append(i)
                if help((pos_row, pos_column), the_board):
                    return True
                # 如果当前位置无法填值, 那么将其值改为原先空的状态, 并将其从board_handled移除
                else:
                    board_handled[pos_row // 3][pos_column // 3].remove(i)
                    the_board[pos_row][pos_column] = '.'

        # 调用主方法
        help((0, 0), board)

        for i in board:
            print(i)


def main():
    solution = Solution()
    tests = [
        # [
        #     ["5", "3", ".", ".", "7", ".", ".", ".", "."],
        #     ["6", ".", ".", "1", "9", "5", ".", ".", "."],
        #     [".", "9", "8", ".", ".", ".", ".", "6", "."],
        #     ["8", ".", ".", ".", "6", ".", ".", ".", "3"],
        #     ["4", ".", ".", "8", ".", "3", ".", ".", "1"],
        #     ["7", ".", ".", ".", "2", ".", ".", ".", "6"],
        #     [".", "6", ".", ".", ".", ".", "2", "8", "."],
        #     [".", ".", ".", "4", "1", "9", ".", ".", "5"],
        #     [".", ".", ".", ".", "8", ".", ".", "7", "9"]
        # ]
        [
            [".", ".", "9", "7", "4", "8", ".", ".", "."],
            ["7", ".", ".", ".", ".", ".", ".", ".", "."],
            [".", "2", ".", "1", ".", "9", ".", ".", "."],
            [".", ".", "7", ".", ".", ".", "2", "4", "."],
            [".", "6", "4", ".", "1", ".", "5", "9", "."],
            [".", "9", "8", ".", ".", ".", "3", ".", "."],
            [".", ".", ".", "8", ".", "3", ".", "2", "."],
            [".", ".", ".", ".", ".", ".", ".", ".", "6"],
            [".", ".", ".", "2", "7", "5", "9", ".", "."]
        ]
    ]
    for board in tests:
        print(solution.solveSudoku(board))


if __name__ == "__main__":
    main()
